MacHack 1997/MacHack 1997.toast/Hacks/Hacks ’97/Warrior’s Progress/source code/Source/Libraries/BitArray/BitArrayBase.cp

Text File | 1997-06-28 | 4.6 KB | 237 lines | [TEXT/CWIE]

// BitArrayBase.cp

#ifndef BitArrayBase_h
#include "BitArrayBase.h"
#endif
#ifndef MinMax_h
#include "MinMax.h"
#endif

BitArrayBase::BitArrayBase( uint32 *theBits,
                                     uint32 theLength )
  : bits( theBits ),
     length( theLength ),
     units( (theLength + unitLength - 1) / unitLength ),
     end( bits + (theLength + unitLength - 1) / unitLength ),
     lastUnitMask( (theLength % unitLength == 0)
                         ? ~0L
                         : (1L << (theLength % unitLength)) - 1 )
  {}

BitArrayBase::BitArrayBase( uint32 *theBits,
                                     uint32 theLength,
                                     bool initialValue )
  : bits( theBits ),
     length( theLength ),
     units( (theLength + unitLength - 1) / unitLength ),
     end( bits + (theLength + unitLength - 1) / unitLength ),
     lastUnitMask( (theLength % unitLength == 0)
                         ? ~0L
                         : (1L << (theLength % unitLength)) - 1 )
  {
    SetAll( initialValue );
    if ( initialValue )
        SetAll();
     else
        ClearAll();
  }

bool BitArrayBase::operator[]( uint32 i ) const
  {
    Assert( i < length );
    return ( bits[ i/unitLength ] & 1L << ( i % unitLength ) ) != 0;
  }

BitReference BitArrayBase::operator[]( uint32 i )
  {
    Assert( i < length );
    return BitReference( bits[ i/unitLength ], i % unitLength );
  }

void BitArrayBase::SetAll( bool value )
  {
    if ( value )
        SetAll();
     else
        ClearAll();
  }

void BitArrayBase::SetAll()
  {
    for ( Unit *p = bits; p < end; p++ )
        *p = ~0L;
  }

void BitArrayBase::ClearAll()
  {
    for ( Unit *p = bits; p < end; p++ )
        *p = 0;
  }

void BitArrayBase::ChangeAll()
  {
    for ( Unit *p = bits; p < end; p++ )
        *p = ~*p;
  }

void BitArrayBase::operator=( const BitArrayBase& r )
  {
    Assert( length == r.length );

    if ( this == &r )
        return;

    Unit *p = bits;
    const Unit *q = r.bits;

    while ( p < end )
        *p++ = *q++;
  }

void BitArrayBase::operator&=( const BitArrayBase& r )
  {
    Assert( length == r.length );

    if ( this == &r )
        return;

    Unit *p = bits;
    const Unit *q = r.bits;

    while ( p < end )
        *p++ &= *q++;
  }

void BitArrayBase::operator|=( const BitArrayBase& r )
  {
    Assert( length == r.length );

    if ( this == &r )
        return;

    Unit *p = bits;
    const Unit *q = r.bits;

    while ( p < end )
        *p++ |= *q++;
  }

void BitArrayBase::operator^=( const BitArrayBase& r )
  {
    Assert( length == r.length );

    if ( this == &r )
      {
        ClearAll();
        return;
      }

    Unit *p = bits;
    const Unit *q = r.bits;

    while ( p < end )
        *p++ ^= *q++;
  }

bool BitArrayBase::operator==( const BitArrayBase& r ) const
  {
    Assert( length == r.length );

    if ( this == &r )
        return true;

    const Unit *last = end - 1;

    Unit *p = bits;
    const Unit *q = r.bits;
    while ( p < last )
        if ( *p++ != *q++ )
            return false;

    return ( (*p ^ *q) & lastUnitMask ) != 0;
  }

uint32 BitArrayBase::FirstZero( uint32 start ) const
  {
    Assert( start <= length );

    Unit *p = bits + start / unitLength;
    if ( p >= end )
        return length;

    Unit skip = ( 1L << (start % unitLength) ) - 1;
    Unit firstUnit = *p | skip;
    if ( firstUnit != ~0L )
      {
        uint32 result = (p - bits) * unitLength + FirstZero( firstUnit );
        return Min( result, length );
      }

    const Unit *last = end - 1;
    for ( p++; p < last; p++ )
        if ( *p != ~0L )
            return (p - bits) * unitLength + FirstZero( *p );

    return (p - bits) * unitLength + FirstZero( *p & lastUnitMask );
  }

uint32 BitArrayBase::FirstOne( uint32 start ) const
  {
    Assert( start <= length );

    Unit *p = bits + start / unitLength;
    if ( p >= end )
        return length;

    Unit skip = ( 1L << (start % unitLength) ) - 1;
    Unit firstUnit = *p & ~skip;
    if ( firstUnit != 0 )
      {
        uint32 result = (p - bits) * unitLength + FirstOne( firstUnit );
        return Min( result, length );
      }

    const Unit *last = end - 1;
    for ( p++; p < last; p++ )
        if ( *p != 0 )
            return (p - bits) * unitLength + FirstOne( *p );

    return (p - bits) * unitLength + FirstOne( *p | ~lastUnitMask );
  }

uint32 BitArrayBase::LastZero( uint32 start ) const
  {
    Assert( start <= length );

    Unit *p = bits + start / unitLength;

    Unit skip = ( 1L << (start % unitLength) ) - 1;
    Unit firstUnit = *p | ~skip;
    if ( firstUnit != ~0L )
        return (p - bits) * unitLength + LastZero( firstUnit );

    for ( p--; p >= bits; p-- )
        if ( *p != ~0L )
            return (p - bits) * unitLength + LastZero( *p );

    return length;
  }

uint32 BitArrayBase::LastOne( uint32 start ) const
  {
    Assert( start <= length );

    Unit *p = bits + start / unitLength;

    Unit skip = ( 1L << (start % unitLength) ) - 1;
    Unit firstUnit = *p & skip;
    if ( firstUnit != 0 )
        return (p - bits) * unitLength + LastOne( firstUnit );

    for ( p--; p >= bits; p-- )
        if ( *p != 0 )
            return (p - bits) * unitLength + LastOne( *p );

    return length;
  }